/*------------------------------------------------------------------------
*
* geqo_erx.c
*	 边重组交叉 [ER]
*
* src/backend/optimizer/geqo/geqo_erx.c
*
*-------------------------------------------------------------------------
*/

/* 贡献者：
   =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
   *  Martin Utesch				 * 自动控制研究所		   *
   =							 = 矿业与技术大学 =
   *  utesch@aut.tu-freiberg.de  * 德国弗赖贝格				   *
   =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
 */

/* 边重组算法采用自 Genitor : */
/*************************************************************/
/*															 */
/*	Copyright (c) 1990										 */
/*	Darrell L. Whitley										 */
/*	计算机科学系									         */
/*	科罗拉多州立大学									     */
/*															 */
/*	特此允许复制本程序的全部或部分以进行自由分发。作者的姓名  */
/*	及本版权声明必须包含在任何复制中。 */
/* geqo_copy
 *
 *	 将一个基因复制到另一个
 *
 */
/*															 */
/*************************************************************/


#include "postgres.h"
#include "optimizer/geqo_random.h"
#include "optimizer/geqo_recombination.h"

#if defined(ERX)

static int	fc_gimme_edge(PlannerInfo *fc_root, Gene fc_gene1, Gene fc_gene2, Edge *fc_edge_table);
static void fc_remove_gene(PlannerInfo *fc_root, Gene fc_gene, Edge fc_edge, Edge *fc_edge_table);
static Gene fc_gimme_gene(PlannerInfo *fc_root, Edge fc_edge, Edge *fc_edge_table);

static Gene fc_edge_failure(PlannerInfo *fc_root, Gene *fc_gene, int fc_index, Edge *fc_edge_table, int fc_num_gene);


/* alloc_edge_table
 *
 *	 为边表分配内存
 *
 */

Edge *
alloc_edge_table(PlannerInfo *fc_root, int fc_num_gene)
{
	Edge	   *fc_edge_table;

	/*
	 * palloc 一个额外的位置，以便可以直接索引编号为 1..n 的节点；
	 * 0 将不被使用
	 */

	fc_edge_table = (Edge *) palloc((fc_num_gene + 1) * sizeof(Edge));

	return fc_edge_table;
}

/* free_edge_table
 *
 *	  释放边表的内存
 *
 */
void free_edge_table(PlannerInfo *fc_root, Edge *fc_edge_table)
{
	pfree(fc_edge_table);
}

/* gimme_edge_table
 *
 *	 填充一个数据结构，表示 (2) 个输入基因之间的显式边的集合
 *
 *	 假设为循环旅行和双向边
 *
 *	 gimme_edge() 将 "共享" 边设置为负值
 *
 *	 返回每个城市的平均边数范围为 2.0 - 4.0
 *	 其中 2.0=同质；4.0=多样
 *
 */
float gimme_edge_table(PlannerInfo *fc_root, Gene *fc_tour1, Gene *fc_tour2,
				 int fc_num_gene, Edge *fc_edge_table)
{
	int			fc_i,
				fc_index1,
				fc_index2;
	int			fc_edge_total;		/* 两个基因中唯一边的总数 */

	/* 首先清除边表的旧数据 */
	for (fc_i = 1; fc_i <= fc_num_gene; fc_i++)
	{
		fc_edge_table[fc_i].total_edges = 0;
		fc_edge_table[fc_i].unused_edges = 0;
	}

	/* 用新数据填充边表 */

	fc_edge_total = 0;

	for (fc_index1 = 0; fc_index1 < fc_num_gene; fc_index1++)
	{
		/*
		 * 假设旅行是循环的，即 1->2, 2->3, 3->1 此操作
		 * 将 n 映射回 1
		 */

		fc_index2 = (fc_index1 + 1) % fc_num_gene;

		/*
		 * 边是双向的，即 1->2 与 2->1 相同，调用 gimme_edge
		 * 每条边两次
		 */

		fc_edge_total += fc_gimme_edge(fc_root, fc_tour1[fc_index1], fc_tour1[fc_index2], fc_edge_table);
		fc_gimme_edge(fc_root, fc_tour1[fc_index2], fc_tour1[fc_index1], fc_edge_table);

		fc_edge_total += fc_gimme_edge(fc_root, fc_tour2[fc_index1], fc_tour2[fc_index2], fc_edge_table);
		fc_gimme_edge(fc_root, fc_tour2[fc_index2], fc_tour2[fc_index1], fc_edge_table);
	}

	/* 返回每个索引的平均边数 */
	return ((float) (fc_edge_total * 2) / (float) fc_num_gene);
}

/* gimme_edge
 *
 *	  在输入边表中注册从 city1 到 city2 的边
 *
 *	  不做方向性假设；
 *	  因此调用例程有责任
 *	  调用 gimme_edge 两次，以在 city1 和 city2 之间创建双向边；
 *	  单向边也是可能的（只需调用 gimme_edge
 *	  一次，从 city1 到 city2 的方向）
 *
 *	  如果边未被注册并刚刚添加，则返回 1；
 *			  如果边已被注册且 edge_table 未更改，则返回 0
 */
static int fc_gimme_edge(PlannerInfo *fc_root, Gene fc_gene1, Gene fc_gene2, Edge *fc_edge_table)
{
	int			fc_i;
	int			fc_edges;
	int			fc_city1 = (int) fc_gene1;
	int			fc_city2 = (int) fc_gene2;


	/* 检查边 city1->city2 是否已存在 */
	fc_edges = fc_edge_table[fc_city1].total_edges;

	for (fc_i = 0; fc_i < fc_edges; fc_i++)
	{
		if ((Gene) Abs(fc_edge_table[fc_city1].edge_list[fc_i]) == fc_city2)
		{

			/* 将共享边标记为负数 */
			fc_edge_table[fc_city1].edge_list[fc_i] = 0 - fc_city2;

			return 0;
		}
	}

	/* 添加 city1->city2; */
	fc_edge_table[fc_city1].edge_list[fc_edges] = fc_city2;

	/* 增加来自 city1 的边的数量 */
	fc_edge_table[fc_city1].total_edges++;
	fc_edge_table[fc_city1].unused_edges++;

	return 1;
}

/* gimme_tour
 *
 *	  使用边表中的边创建新的旅行。
 *	  优先选择 "共享" 边（即所有父基因拥有并在边表中标记为负的边）。
 *
 */
int gimme_tour(PlannerInfo *fc_root, Edge *fc_edge_table, Gene *fc_new_gene, int fc_num_gene)
{
	int			fc_i;
	int			fc_edge_failures = 0;

	/* 在 1 和 num_gene 之间选择整数 */
	fc_new_gene[0] = (Gene) geqo_randint(fc_root, fc_num_gene, 1);

	for (fc_i = 1; fc_i < fc_num_gene; fc_i++)
	{
		/*
		 * 当每个点被加入旅行时，从边表中移除它
		 */

		fc_remove_gene(fc_root, fc_new_gene[fc_i - 1], fc_edge_table[(int) fc_new_gene[fc_i - 1]], fc_edge_table);

		/* 找到新加入点的目的地 */

		if (fc_edge_table[fc_new_gene[fc_i - 1]].unused_edges > 0)
			fc_new_gene[fc_i] = fc_gimme_gene(fc_root, fc_edge_table[(int) fc_new_gene[fc_i - 1]], fc_edge_table);

		else
		{						/* 处理故障 */
			fc_edge_failures++;

			fc_new_gene[fc_i] = fc_edge_failure(fc_root, fc_new_gene, fc_i - 1, fc_edge_table, fc_num_gene);
		}

		/* 将此节点标记为已合并 */
		fc_edge_table[(int) fc_new_gene[fc_i - 1]].unused_edges = -1;
	}							/* for (i=1; i<num_gene; i++) */

	return fc_edge_failures;
}

/* remove_gene
 *
 *	 从 edge_table 中移除输入基因。
 *	 输入边用于识别在 edge 表中的删除位置。
 *
 */
static void fc_remove_gene(PlannerInfo *fc_root, Gene fc_gene, Edge fc_edge, Edge *fc_edge_table)
{
	int			fc_i,
				fc_j;
	int			fc_possess_edge;
	int			fc_genes_remaining;

	/*
	 * 对每个已知与输入基因有边的基因执行操作（即在
	 * 输入边的 edge_list 中）
	 */

	for (fc_i = 0; fc_i < fc_edge.unused_edges; fc_i++)
	{
		fc_possess_edge = (int) Abs(fc_edge.edge_list[fc_i]);
		fc_genes_remaining = fc_edge_table[fc_possess_edge].unused_edges;

		/* 在所有 edge_lists 中查找输入基因并删除它 */
		for (fc_j = 0; fc_j < fc_genes_remaining; fc_j++)
		{

			if ((Gene) Abs(fc_edge_table[fc_possess_edge].edge_list[fc_j]) == fc_gene)
			{

				fc_edge_table[fc_possess_edge].unused_edges--;

				fc_edge_table[fc_possess_edge].edge_list[fc_j] =
					fc_edge_table[fc_possess_edge].edge_list[fc_genes_remaining - 1];

				break;
			}
		}
	}
}

/* gimme_gene
 *
 *	  优先考虑 "共享" 边
 *	  (即两个基因都有的边)
 *
 */
static Gene
fc_gimme_gene(PlannerInfo *fc_root, Edge fc_edge, Edge *fc_edge_table)
{
	int			fc_i;
	Gene		fc_friend;
	int			fc_minimum_edges;
	int			fc_minimum_count = -1;
	int			fc_rand_decision;

	/*
	 * 没有点的边指向超过 4 个其他点，因此，这个人为的
	 * 最小值将被替换
	 */

	fc_minimum_edges = 5;

	/* 考虑边列表中的候选目标点 */

	for (fc_i = 0; fc_i < fc_edge.unused_edges; fc_i++)
	{
		fc_friend = (Gene) fc_edge.edge_list[fc_i];

		/*
		 * 优先考虑负的共享边；因此返回它们
		 */

		/*
		 * 负值在这里被捕获，因此我们不需要担心
		 * 转换为绝对值
		 */
		if (fc_friend < 0)
			return (Gene) Abs(fc_friend);


		/*
		 * 优先考虑拥有最少剩余未使用边的候选者；
		 * 找出最小未使用边的数量
		 * (minimum_edges)；如果有多个候选者拥有
		 * 最小未使用边的数量，则计算这个数字
		 * (minimum_count)；
		 */

		/*
		 * 对 minimum_count 的测试可能在某个时候可以移除
		 * 但注释应该明确说明为什么能保证
		 * 测试在第一次运行时总会成功。如果它可能
		 * 失败，那么代码就是错误的
		 */


		if (fc_edge_table[(int) fc_friend].unused_edges < fc_minimum_edges)
		{
			fc_minimum_edges = fc_edge_table[(int) fc_friend].unused_edges;
			fc_minimum_count = 1;
		}
		else if (fc_minimum_count == -1)
			elog(ERROR, "minimum_count not set");
		else if (fc_edge_table[(int) fc_friend].unused_edges == fc_minimum_edges)
			fc_minimum_count++;
	}							/* for (i=0; i<edge.unused_edges; i++) */


	/* 在可用候选者中随机做出决定 */
	fc_rand_decision = geqo_randint(fc_root, fc_minimum_count - 1, 0);


	for (fc_i = 0; fc_i < fc_edge.unused_edges; fc_i++)
	{
		fc_friend = (Gene) fc_edge.edge_list[fc_i];

		/* 返回所选择的候选点 */
		if (fc_edge_table[(int) fc_friend].unused_edges == fc_minimum_edges)
		{
			fc_minimum_count--;

			if (fc_minimum_count == fc_rand_decision)
				return fc_friend;
		}
	}

	/* ... 应该永远不会到达 */
	elog(ERROR, "neither shared nor minimum number nor random edge found");
	return 0;					/* 以保持编译器安静 */
}

/* edge_failure
 *
 *	  处理边失败的例程
 *
 */
static Gene
fc_edge_failure(PlannerInfo *fc_root, Gene *fc_gene, int fc_index, Edge *fc_edge_table, int fc_num_gene)
{
	int			fc_i;
	Gene		fc_fail_gene = fc_gene[fc_index];
	int			fc_remaining_edges = 0;
	int			fc_four_count = 0;
	int			fc_rand_decision;


	/*
	 * 还有多少条边？还剩下多少个有四条总（初始）边的基因？
	 */

	for (fc_i = 1; fc_i <= fc_num_gene; fc_i++)
	{
		if ((fc_edge_table[fc_i].unused_edges != -1) && (fc_i != (int) fc_fail_gene))
		{
			fc_remaining_edges++;

			if (fc_edge_table[fc_i].total_edges == 4)
				fc_four_count++;
		}
	}

	/*
	 * 在剩余边中随机选择有四条边的基因
	 */

	if (fc_four_count != 0)
	{

		fc_rand_decision = geqo_randint(fc_root, fc_four_count - 1, 0);

		for (fc_i = 1; fc_i <= fc_num_gene; fc_i++)
		{

			if ((Gene) fc_i != fc_fail_gene &&
				fc_edge_table[fc_i].unused_edges != -1 &&
				fc_edge_table[fc_i].total_edges == 4)
			{

				fc_four_count--;

				if (fc_rand_decision == fc_four_count)
					return (Gene) fc_i;
			}
		}

		elog(LOG, "no edge found via random decision and total_edges == 4");
	}
	else if (fc_remaining_edges != 0)
	{
		/* 在剩余边中随机选择基因 */
		fc_rand_decision = geqo_randint(fc_root, fc_remaining_edges - 1, 0);

		for (fc_i = 1; fc_i <= fc_num_gene; fc_i++)
		{

			if ((Gene) fc_i != fc_fail_gene &&
				fc_edge_table[fc_i].unused_edges != -1)
			{

				fc_remaining_edges--;

				if (fc_rand_decision == fc_remaining_edges)
					return fc_i;
			}
		}

		elog(LOG, "no edge found via random decision with remaining edges");
	}

	/*
	 * 边表似乎是空的；这有时发生在最后一点
	 * 由于第一个点在表中被移除，即使只有一条边已确定
	 */

	else
	{							/* 仅在巡回中的最后一个点发生；
								 * 只是寻找尚未
								 * 使用的点 */

		for (fc_i = 1; fc_i <= fc_num_gene; fc_i++)
			if (fc_edge_table[fc_i].unused_edges >= 0)
				return (Gene) fc_i;

		elog(LOG, "no edge found via looking for the last unused point");
	}


	/* ... 应该永远不会到达 */
	elog(ERROR, "no edge found");
	return 0;					/* 以保持编译器安静 */
}

#endif							/* defined(ERX) */
